package com.copa.l589;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author copa
 * @createDate 2022-08-30 10:12
 * @function 迭代法
 */
public class Test2 {

    public List<Integer> preorder(Node root) {
        if (root == null) {
            // 测试用例要求返回空集合
            return new ArrayList<>();
        }
        List<Integer> result = new ArrayList<>();
        Stack<Node> stack = new Stack<>();
        stack.add(root);
        while (stack.size() > 0) {
            Node node = stack.pop();
            result.add(node.val);
            if (node.children != null) {
                // 依据栈的特性，从右到左遍历孩子节点
                for (int i = node.children.size() - 1; i >= 0; i--) {
                    stack.push(node.children.get(i));
                }
            }
        }
        return result;
    }


    public static void main(String[] args) {
        Node root = new Node(1);
        List<Node> child1 = new ArrayList<>();
        child1.add(new Node(3));
        child1.add(new Node(2));
        child1.add(new Node(4));
        root.children = child1;
        List<Node> child2 = new ArrayList<>();
        child2.add(new Node(5));
        child2.add(new Node(6));
        child1.get(0).children = child2;
        for (Integer result : new Test2().preorder(root)) {
            System.out.print(result + "\t");
        }

    }
}
